package com.agan.aganalgorithm.graph.depthfirst;

import java.util.Iterator;

/**
 * @ClassName GraphTraversal 深度优先算法
 * @Description
 **/
public class GraphTraversal {

    /**
     * 链表 -有向图实现
     */
    LinksGraph graph;

    /**
     * 记录那些顶点已经被访问过
     */
    boolean[] visited;

    public GraphTraversal(LinksGraph linksGraph){
        this.graph = linksGraph;
        visited = new boolean[linksGraph.graphs.size()];
    }
    public void DFS(){
        for (int i =0;i<graph.graphs.size();i++){
            if(!visited[i]){
                DFSTraversal(i);
            }
        }
    }
    /**
     *  单个顶点
     * @param v
     */
    public void DFSTraversal(int v){
        if(visited[v]) return;
        visited[v] = true;
        System.out.println(v + "->");
        Iterator<Integer> neighbors = graph.graphs.get(v).iterator();
        while (neighbors.hasNext()){
            int nextNode = neighbors.next();
            if(!visited[nextNode]){
                DFSTraversal(nextNode);
            }
        }

    }
}
